package com.yq.dataStructures.tree.threadedBinaryTree;

/**
 * @ClassName ThreadedBinaryTreeDemo
 * @Description TODO
 * @Author yaoqiang
 * @Date 2021/11/15 14:11
 * @Version 1.0
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        Node root = new Node(1, "1");
        Node node2 = new Node(3, "3");
        Node node3 = new Node(6, "6");
        Node node4 = new Node(8, "8");
        Node node5 = new Node(10, "10");
        Node node6 = new Node(14, "14");

        //创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        //测试中序线索化

        ThreadedBinaryTree tree=new ThreadedBinaryTree();
        tree.setRoot(root);
        tree.threadedNodes();
        //测试10号节点
            Node leftNode=node5.getLeft();
            Node rightNode=node5.getRight();
        System.out.println("10号的前驱节点"+leftNode.getNo());//3
        System.out.println("10好节点的后续节点是"+rightNode.getNo());//1
        //线索化方式遍历二叉树8310,1,14,6
        tree.threadedList();
    }
}


class Node {
    private int no;
    private String name;
    private Node left;
    private Node right;
    //如果leftType==0表示指向左子树，如果是1则表示指向前驱节点
    private int leftType;
    private int rightType;


    public Node(int no, String s) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

}

class ThreadedBinaryTree{
    private Node root;
    //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针。在递归进行线索化时，pre总保留前一个节点
    private Node pre=null;

    public void setRoot(Node root) {
        this.root = root;
    }

    public void threadedNodes(){
        threadedNodes(root);
    }

    public void threadedNodes(Node node){
        if(node==null){return;}
        //线索化左子树
        threadedNodes(node.getLeft());
        if(node.getLeft()==null){
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点做指针的类型，指向前驱节点
            node.setLeftType(1);
        }
        //处理后续节点
        if(pre!=null && pre .getRight()==null){
            //让前驱的右指针指向当前节点,并修改右指针类型
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre=node;
        //序列化右子树
        threadedNodes(node.getRight());
    }


    public void threadedList() {
        Node node=root;
        while (node!=null){
            //循环找到leftType==1的结点，第一个找到的就是8节点
            //当leftType=1时，该节点按照线索化处理
            while (node.getLeftType()==0){
                node=node.getLeft();
            }
            System.out.println(node.getNo());
            //如果当前节点的右指针指向的是后继节点，就一直输出
            while (node.getRightType()==1){
                node=node.getRight();
                System.out.println(node.getNo());
            }
            node=node.getRight();
        }
    }
}